package developer.算法.回溯.电话号码的字母组合;

import java.util.*;

/**
 * @author zhangyongkang
 * @time 2025/4/1 16:34
 * @description 示例 1：
 * <p>
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 示例 2：
 * <p>
 * 输入：digits = ""
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 */
public class DianHuaHaoMaDeZiMuZuHe {

    public static void main(String[] args) {

        Solution3 solution = new Solution3();
        List<String> strings = solution.letterCombinations("22");
        System.out.println(strings);
    }


    static class Solution3 {
        Map<String, List<String>> numMap = new HashMap<String, List<String>>() {
            {
                put("2", Arrays.asList("a", "b", "c"));
                put("3", Arrays.asList("d", "e", "f"));
                put("4", Arrays.asList("g", "h", "i"));
                put("5", Arrays.asList("j", "k", "l"));
                put("6", Arrays.asList("m", "n", "o"));
                put("7", Arrays.asList("p", "q", "r", "s"));
                put("8", Arrays.asList("t", "u", "v"));
                put("9", Arrays.asList("w", "x", "y", "z"));
            }
        };

        private List<String> result;
        private int max;

        public List<String> letterCombinations(String digits) {
            result = new ArrayList<>();
            max = digits.length();
            Set<String> total = new HashSet<>();
            for (String s : digits.split("")) {
                total.addAll(numMap.get(s));
            }
            dfs(
                    new StringBuilder(),
                    total
            );
            return result;
        }

        private void dfs(
                StringBuilder current,
                Set<String> total
        ) {
            if (current.length() == max) {
                result.add(current.toString());
                return;
            }

            for (String s : total) {//不用考虑是否重复 电话号码是可以重复的
                current.append(s);
                dfs(current, total);
                current.deleteCharAt(current.length() - 1);
            }

        }

    }


    static class Solution {
        Map<String, List<String>> numMap = new HashMap<String, List<String>>() {
            {
                put("2", Arrays.asList("a", "b", "c"));
                put("3", Arrays.asList("d", "e", "f"));
                put("4", Arrays.asList("g", "h", "i"));
                put("5", Arrays.asList("j", "k", "l"));
                put("6", Arrays.asList("m", "n", "o"));
                put("7", Arrays.asList("p", "q", "r", "s"));
                put("8", Arrays.asList("t", "u", "v"));
                put("9", Arrays.asList("w", "x", "y", "z"));
            }
        };


        public List<String> letterCombinations(String digits) {
            if (digits.isEmpty()) {
                return new ArrayList<>();
            }
            List<String> res = new ArrayList<>();
            List<List<String>> nums = new ArrayList<>();
            for (String num : digits.split("")) {
                nums.add(numMap.get(num));
            }
            dfs(null, 0, nums, res);
            return res;
        }

        public void dfs(List<String> last, int level, List<List<String>> totals, List<String> result) {
            if (totals.size() == level) {
                result.add(String.join("", last));
                return;
            }

            for (String s : totals.get(level)) {
                if (level == 0) {
                    last = new ArrayList<>();
                }
                last.add(s);
                dfs(last, level + 1, totals, result);
                last.remove(last.size() - 1);
            }

        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/388738/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class SolutionOfficial {
        public List<String> letterCombinations(String digits) {
            List<String> combinations = new ArrayList<String>();
            if (digits.length() == 0) {
                return combinations;
            }
            Map<Character, String> phoneMap = new HashMap<Character, String>() {{
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
            return combinations;
        }

        public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
            if (index == digits.length()) {
                combinations.add(combination.toString());
            } else {
                char digit = digits.charAt(index);
                String letters = phoneMap.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
                    combination.append(letters.charAt(i));
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }
    }

}
